import java.util.ArrayList;
import java.util.List;

/**
 * 1175. 质数排列
 * https://leetcode-cn.com/problems/prime-arrangements/
 */
public class Solutions_1175 {
    public static void main(String[] args) {
        int n1 = 5;  // output: 12
        int n2 = 100;  // output: 682289015

        List<Integer> inputs = new ArrayList<>();
        inputs.add(n1);
        inputs.add(n2);

        for (int input : inputs) {
            int result = numPrimeArrangements(input);
            System.out.println(result);
        }
    }

    /**
     * 结果为素数的组合排列数 * 非素数的组合排列数
     * 3 个数的组合排列数为 6 种，即 3 的阶乘：1 * 2 * 3
     * 4 个数的组合排列数为 24 种，即 4 的阶乘：1 * 2 * 3 * 4
     */
    public static int numPrimeArrangements(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        int mod = 1_000_000_007;
        // 数字 2 本身就是素数
        int primeCnt = 1;

        for (int i = 3; i <= n; i++) {
            boolean flag = isPrime(i);
            if (flag) {
                primeCnt ++;
            }
        }
        long res1 = 1L, res2 = 1L;
        // 素数能够组合的排列数
        for (int i = 2; i <= primeCnt; i++) {
            res1 = (res1 * i) % mod;
        }
        // 非素数能够组合的排列数
        for (int i = 2; i <= n - primeCnt; i++) {
            res2 = (res2 * i) % mod;
        }
        return (int) ((res1 * res2) % mod);
    }

    /**
     * 判断 n 是否为素数
     */
    public static boolean isPrime(int n) {
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
}
